/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package kleinberg;

import java.util.ArrayList;
import java.util.Collections;

/**
 *
 * @author veena
 */
public class TrialSingleStream {
    
    double gamma=1;
    double gammalogn=0;
    double s=2;//scaling parameter
    double n=0;//length of gaps
    double T=0;//total of all gaps
    double g=0;//n/T
    double min=0;//min of gaps
    double kstates=0,add=0;//no. of states reqd for optimal state transition
    ArrayList<Double> alpha=new ArrayList<Double>();
    ArrayList<Integer> gaps=new ArrayList<Integer>();
    ArrayList<Double> cost=new ArrayList<Double>();
//        ArrayList<Double> c=new ArrayList<Double>();
        ArrayList<Double> costprime=new ArrayList<Double>();
        
        ArrayList<ArrayList<Double>> C=new ArrayList<ArrayList<Double>>();
        
        ArrayList<Double> tmp=new ArrayList<Double>();
        
        ArrayList<ArrayList<Double>> q;
        ArrayList<ArrayList<Double>> qprime;
    public static void main(String[] args){
        
        TrialSingleStream tss=new TrialSingleStream();
        tss.calculated();
    }
    //single stream given offsets calculate ebursts and plot it 
    private void calculated(){
                TrialSingleStream tss=new TrialSingleStream();

        double val=0,term1=0,term2=0,temp=0;
        //take the inputs and process them
        int diff=0,st=0,ed=0,minindex=0;
                q = new ArrayList<ArrayList<Double>>();

        qprime = new ArrayList<ArrayList<Double>>();
        
//        cost = new int[][];
        int[] offsets={0,100,200,300,400,410,415,420,425,430,435,440,445,450,451,453,455,457,459,461,463,465,467,469,480,485,490,495,500,505,510,515,520,525,530,535,540,545,550,555,560,565,570,575,580,585,590,595,600,700,710,715,720,725,730,735,740,745,750,755,760,765,770,775,780,785,790,795,800,900,1000};
                //calculate gaps, n and T here

    //input offssets
        
//calculate gaps
        //generate gaps now 
        for(int i=0;i<offsets.length-1;i++){
            if((i+1)<offsets.length)
            st=offsets[i+1];
            
            ed=offsets[i];
                diff=st-ed;
                gaps.add(diff );
                T+=diff;
        
        }
        diff=0;
        n=gaps.size();
        g=T/n;
        min=Double.valueOf(Collections.min(gaps));
        kstates=Math.ceil(1+tss.logOfBase(s, T)+tss.logOfBase(s, (1/min)));
       
        for(int i=0;i<kstates;i++){
            val=Math.pow(s, i)/g;
            alpha.add(val);
//            System.out.println(alpha.get(i));
        }
        gammalogn=gamma*Math.log(n);
        //intitialization
//        c.set(0 , 0.0);c.set((int) kstates, 100000.0);//cost of size k
        for(int i=0;i<kstates;i++){//q of size k*t
            q.add(new ArrayList<Double>());
//            q.get(i).set(i, 0);
            
                C.add(new ArrayList<Double>());
                for(int t=0;t<n;t++){
                    C.get(i).add(0.0);
                }
//                C.get(i).add(0.0);
               
        }
        System.out.println(C.size());
        //dynamic programming cost
      for(int t=0;t<n;t++){
            //init inside
//            qprime=new ArrayList<>();
//        for(int i=0;i<kstates;i++){
//            costprime=new ArrayList<>();
//            qprime.add(new ArrayList<Double>());
//            for(int ii=0;ii<t;ii++){ 
//                qprime.get(i).add(Double.valueOf(String.valueOf(i)));
//            }
//        }//init qprime 
//          for(int i=0;i<kstates;i++){//q of size k*t
//              
//            qprime.get(i).add(new ArrayList<Double>());
////            costprime.add(Double.POSITIVE_INFINITY);
////            qprime.get(i).set(t, Double.POSITIVE_INFINITY);
//        }  
          
      //end init
            for(int j=0;j<kstates;j++){
                term1=alpha.get(j)*gaps.get(t)-Math.log(alpha.get(j));
                for(int l=0;l<kstates;l++){
                    //called cost
                    double tau=(j-l)*gammalogn;
                    if(t==0){
                    temp=tau+C.get(l).get(0);
                    }
                    else{
                       temp=tau+C.get(l).get(t-1);
                    }
                    if(temp<0)
                        cost.add(0.0);
                    else
                       cost.add(temp);
                }
                temp=Collections.min(cost);
                if(temp>=0){
                    add=cost.get((int) temp)+term1;
//                    System.out.println("P1:"+add+" t:"+t+" j:"+j);
                     C.get(j).set(t,add);
                }else{
                    if(t==0){
                        C.get(j).set(t,0.0);
                    }else
//                        System.out.println("P2:"+add);
                     C.get(j).set(t,C.get(j).get(t-1));
                }
               
                
            }
            
//            System.out.println(C.size());
           
        }
      for(int i=0;i<C.size();i++){
        for(int t=0;t<n;t++){
          System.out.print(C.get(i).get(t)+":");
        }
        System.out.println();
      }
    }
      
    private double logOfBase(double base, double num) {
    return Math.log10(num) / Math.log10(base);
}
    
}

